package com.gitee.feizns.explore.data_structure.tree.bs.mid;


import java.util.LinkedList;
import java.util.Queue;

/**
 * @author feizns
 * @since 2020/3/9
 */
public class Connect {

    public static void main(String[] args) {

    }

    public static Node connect(Node root) {
        if ( root != null ) {
            Queue<Node> ret = new LinkedList<>();
            ret.add(root);
            levelOrder(ret);
        }
        return root;
    }

    private static void levelOrder(Queue<Node> nodes) {
        Queue<Node> newQueue = new LinkedList<>();
        Node prev = null;
        while ( !nodes.isEmpty() ) {
            Node node = nodes.remove();
            if ( prev != null )
                prev.next = node;
            if ( node.left != null )
                newQueue.add(node.left);
            if ( node.right != null )
                newQueue.add(node.right);
            prev = node;
        }
        if ( !newQueue.isEmpty() )
            levelOrder(newQueue);
    }

    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };

}
